HPAVC/HPAVC CD-ROM.iso/CIS_GAME.ARJ/QVOXL2.THD

Text File | 1993-06-25 | 43KB | 896 lines

______________________________ Subj: Oct Trees ______________________________

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Dan Corritore 70243,1110 (X)

>> I remember that discussion, although I don't recall
   anything about using trees in it, but then again,

[ Editor's note: see VOXEL.THD, GAMERS section 11 ]

That subject, which Chris Lampton, at least, knows a lot more about then I,
involves using an Octree (a tree where each node has eight links). I believe
it's done this way (Chris, jump in and tell me far off I am <g>):

You consider your world space as a cube (or in your case a 2D rectangle)
which is subdivided into eight interior cubes, each of which has a link
pointer in the parent cube (in the case of the children of the root node,
their parent is the world space. Within each node, a child pointer is null
(the cube of space is undefined) if there is nothing in it, or has a pointer
to a node if there is. That node is then subdivided according to the same
rule. Each of the cubes is known as a Voxel. The advantage is that you do not
store positional data for cubes (or rectangles) of empty space. As I remember
this is most applicable to flight simulators, where huge portions of the
world database contain nothing at all. In your case I could see using a
quadtree (as above, with a four-level subdivision of a 2D rectangle). Each
node would contain the rectangle extents, and a linked list of objects
present in that rectangle.
                                                --Mark
...........................................................................

Fm: Dan Corritore 70243,1110
To: Mark Betz/Ass't SysOp 76605,2346 (X)

What you said sounds almost exactly like what Kevin Gliner suggested. In
fact, it sounds a whole lot like tiles, although a tile wouldn't have a
linked list, and it wouldn't be on a tree. Which is one thing I can't
understand with what you said.. why not just have an array (the size of the
smallest subdivision you have*(size of the world/subdivision) or something as
such), with linked list pointers coming off of them? That way, you wouldn't
have to traverse the tree to get to a certain section, only to traverse a
linked list afterwards.         What I'm using for my tree stuff isn't like
that.. well, actually, I do have a few subdivisions of the world (if it's
32000*32000 pixels, the first node would be at 16000*16000, etc.. until a
suitable enough division is reached.. of course, I could just use an array of
tree's starting at those divisions), but I put the objects into their correct
places(not on linked lists--each object has child pointers which are
traversed based on compares).         I hope you understood that..(and I hope
I understood you correctly<g>)
   Thanks,
        _Dan
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Dan Corritore 70243,1110

Well, the biggest reason is that, with an array, you'd have to check every
element to see if the linked list was empty or not. With the Octree, if the
space defined by the child pointer is empty, then the pointer is null.

                                                        --Mark
...........................................................................

Fm: Hans Peter Rushworth 100031,473
To: Dan Corritore/MOTM 70243,1110

An array would be preferred if you were interested in all points in the 3D
space, even parts that are not visible. In most cases you are interested only
where a surface lies in the the 3D space.

You could store such a surface in a pair of 2D arrays where one array is used
to indicate the altitude of a point in the surface, and the other array is
used to store say a colour value for that point. The first problem with this
if you have a vertical feature like a cliff, you store less surface detail
than where the surface is a plain (which is usually less "interesting"). The
second problem is that even if there are large areas of no interest, the
storage still needs to be allocated for that area.

With a voxel approach, memory is only used where detail is present, and where
the surface exists. Since the voxel structure is fractal, you can add extra
detail to cater for special situations that have a lot of detail, and the
problem of "cliffs" is much less of a problem.

For very large 3D spaces, octree (voxel) storage schemes are much more
efficient than arrays, and they have the added benefit of "adaptive"
resolution control, wherein you restrict the depth of your search for more
distant objects.

In practice you might use a hybrid approach, say have an octree of arrays.
The arrays are there to provide detail that is easier to process (as you say)
You might call this array a voxary <g>

Peter.
...........................................................................

Fm: Hans Peter Rushworth 100031,473
To: John W. Ratcliff 70253,3237 (X)

No John, I have no connection with the commanche people. I'm led to believe
they did not use the voxel surface representation (as I described it) because
in CMO the areas with large change in altitude give rise to "tall rectangles"
which is the result you would get when using two 2D arrays for colour and
altittude. (Unless I remember incorrectly).

Of course it's still possible they used a quadtree in place of either of the
2D arrays, but this would not be computationally efficient IMO.

I have looked at CONTOUR.ZIP and I would agree that CMO probably uses a
similar minmax method to mask displayed pixels in the vertical, but there is
still the problem of ordering the surface altitudes, and I'm not sure what
method you used for that, or whether CMO uses a similar or novel approach.

I have implemented a high speed display system using a different sort of tree
(a Binary Space Partitioning Tree), which was mainly used for hidden surface
removal of polygon data. The BSP tree when appropriately traversed visits
nodes in order of distance, irrespective of the view position. The BSP system
IMO is a very efficient for static, non-intersecting databases.

As for CMO, I suspect they simply calculate the vanishing points of the
horizon where it meets the screen edges (which it is contrived to do always),
and together with the mappings of the bottom edge screen co-ordinates, find a
4-point mapping into their altitude and colour arrays. It is then a simple
matter to use incremental interpolation to sample a vertical "slice"
representing colour and altitudes for each display pixel, and then paint them
using the minmax hidden surface method. I have used a similar sampling scheme
to map flat texture maps into arbitrarily oriented 3D polygons, and using
incremental sampling, the speed can be very fast, even in C.

The sampling scheme automatically deals with the replication and skipping of
map pixels (if the map is visually very close, the same point is sampled more
than once, if distant, pixels are "missed out"). Rotations are dealt with by
transforming only the initial 4 screen corner points. All interpolated
samples that are taken using these points are implicitly rotated.

I could probably knock up a program to demonstrate this using a fractal
plasma surface if you are interested, but you might have to wait a week or
two.

Peter.
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Hans Peter Rushworth 100031,473 (X)

>> voxarray

I love it! Patent that fast <g>.

I'm no expert on Octrees, but I think I have the basic concept down. What I'm
wondering is what information you consider it necessary to store in each node
of the tree. I'm thinking that, since the node represents a cube, you have to
define the cube's extent. You then have to have a way to travel to the
structures defining the objects in the space. This might be a pointer to a
linked list of objects.

The most puzzling question (at this moment): since the voxel space is
recursively divisible down to a cube of 1 unit on a side, at what point do
you stop and say "this is the cube the object or feature exists in". This is
related to your mention of resolution, but I'm confused as to how to apply
it.
                                                        --Mark
...........................................................................

Fm: Hans Peter Rushworth 100031,473
To: Mark Betz/Ass't SysOp 76605,2346 (X)

>> I'm thinking that, since the node represents a cube, you have to define
the cube's extent.

I don't think so Mark. Imagine your 3D space was 1Km x 1Km x 1Km. The root
node of the octree is a cube of those dimensions. If you subdivide this node,
a child of this node is a cube 500m x 500m x 500m (ie one eigth the volume).
The extent of the cube is always known by reference to its depth in the
hierarchy. When "expanding" the octree, you stop when the cube dimensions
would be "the same size as a pixel". If you don't subdivide this way, you
have to do extra checks to make sure you don't have overlapping and
inconsistent spaces. There is no limit to the amount you can subdivide the 3D
space - it is fractal.

>> what to store in the node.

You might store a mean value (lets say colour, or material) of whatever is
stored in children of the node. You can use this value when you decide not to
proceed further in processing the tree.

>> The most puzzling question (at this moment): since the voxel space is
recursively divisible down to a cube of 1 unit on a side, at what point do
you stop and say "this is the cube the object or feature exists in". This is
related to your mention of resolution, but I'm confused as to how to apply
it.

Say your 3D space represents oil trapped beneath the surface of the earth.
The resolution limit might be determined by how big a drill bit you have, or
how large an volume of oil is worth drilling a hole for.

It all depends on what you want to use the octree for.

Peter.
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Hans Peter Rushworth 100031,473 (X)

I think I see, Peter. The extent of the cube is determined by the division of
the parent cube. The actual location of the child space inside the parent
cube is determined by it's position, i.e. top-left, middle-center, etc.

I assume that the reason you put "pixel" in quotes is that the size of the
pixel is not always one screen pixel. You might have a rectangular solid that
is ten screen pixels on a side, and so you don't deal with it in any finer
resolution.

Am I getting close? There is a good discussion of Voxels in Foley, Van Dam,
et al. I'll have to have a look at it tomorrow.

                                                        --Mark
...........................................................................

Fm: Hans Peter Rushworth 100031,473
To: Mark Betz/Ass't SysOp 76605,2346 (X)

>> Am I getting close?

Yes. It doesn't really matter about what you use it for, and therefore what
represents what. The important thing is to realise that the organisation or
"shape" of the tree actually tells you something about the space.

Another interesting aspect is that you can directly get the co-ordinates of
a particular voxel by knowing what route you took to get to it. Each node has
upto 8 subtrees. If you number these links 0 to 7, and organise the links so
that the *bits* in the *link number* indicate the 1-bit "co-ordinates" of the
children in XYZ relative to this node where the X Y & Z bits are bits 0,1 and 2
respectively <thats tricky to explain!>, and as you descend the tree with a
max depth "n" you store the bit number in a list, the co-ordinates (xyz) of
current node is:

   x = 0; y = 0; z = 0;
   for(int i=0;i<depth;i++)
   {
      int bit = 1<<(n-i);
      if(list[i] & 1) x += bit;
      if(list[i] & 2) y += bit;
      if(list[i] & 4) z += bit;
   }

Working the other way, it is easy to see a way of finding the nearest node
to a point in the space given the X,Y and Z co-ordinates.

Again, assuming "n" is the max depth of the tree:

typedef struct vox_node {
   struct vox_node *link[8]; // pointers to children
   VOX_DATA data;            // whatever...
} VOX_NODE;

  VOX_NODE *current = root,*tmp;
      // unsigned so "n" can be upto 16 ;)
  for(unsigned mask = (1<<(n-1)) ; mask ; mask >>= 1)
  {
      probe = current->link[ ((x & mask) ? 1 : 0) +
                             ((y & mask) ? 2 : 0) +
                             ((z & mask) ? 4 : 0) ];
     if(!probe) break;
     current = probe;
  }
  // Now "current" points at nearest voxel

(sorry about all the shifts, this would be much easier in assembler <g>).
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632
To: Hans Peter Rushworth 100031,473 (X)

Hi Peter,

There was an article a few months ago in C Users Journal that concerned
quad-trees and quad-codes.  With a quad-code is was possible to represent
any two-dimensional region.  I suppose your oct-tree is the same idea, and
if you take it further you could encode an oct-code representing any
3-dimensional object.  Have you seen the article I'm talking about?

Bob

__________________________ Subj: RGB to Oct Tree ___________________________

Fm: Bob Provencher/GD SL 71621,2632
To: Mark Betz/Ass't SysOp 76605,2346 (X)

Hi Mark!

I was thinking about the RGB to octal-code problem, and I discovered the
answer, it turned out to be deceptively simple!  I'll follow through my
thinking to see if you agree with my conclusions.

If you set up your octants so that they correspond to increases in the R, G,
and B directions such that an increase in the R (or x) direction adds 2^0 to
the octant number, an increase in the G adds 2^1, and B adds 2^2 then you
come up with an octant map that looks something like this:

    111                 7
101     110         5       6
    100                 4

    011                 3
001     010         1       2
    000                 0

So compute the octant of an rgb value, you simply decide whether it is the
second half of the line which describes the componant you're looking for.

So, for example, assuming a cube 63 on a side, the first octant for the rgb
value 32,32,32 is 1,1,1 or 7.  However, 31, 31, 31 is in octant 0,0,0.

Now what is really interesting, is that if you examine the values you get,
it turns out the computing the octant is a very straightforward.  At each
step, to see if a value lays within the first or second half of the desired
line, you need only examine the current high bit.

What this means is that you can compute the oct-code down to the desired
6 octants by simply rotating the bit field that represents the RGB value!

For example:

RGB  63, 31, 0       RGB 0, 0, 0         RGB 63, 0, 63 (Purple)

B - 000000  2^2      B - 000000          B - 111111
G - 011111  2^1      G - 000000          G - 000000
R - 111111  2^0      R - 000000          R - 111111
    ------               ------              ------
 Oct 133333               000000              555555

So, it's very easy to compute the oct-code, and as we discussed to find RGB
values in the same region as the desired one, you only need examine those
with the same leading 5 digits.  This will give you the seven values to the
right and up from the desired one.  If you were to examine the oct-codes
that had the same 4 leading digits, you would then get values, that could be
to the left of the desired one.

If you use the leading 4 digits, worst case would be 64 matches (highly
unlikely in a 256 color pallette).  At that point you'd need to do your
3-d distance computation, but, if you think about it, you only need to
examine the lowest two bits!  The max distance here would only be 4, so the
max square root you'd need to compute would be 32!  These could easily be
stored in a small lookup table.

What do you think?

Bob
...........................................................................

Fm: Dan Corritore/MOTM 70243,1110
To: Hans Peter Rushworth 100031,473 (X)

I'm sorry, but I still don't understand exactly how this tree structure
works, and, from what Mark said, it sounded like it wastes as much (actually,
more) space as an array, since you have the tree divided up into sections,
and each section either has a null pointer or a linked list.. an array would
have the same stuff, in less space, and less accessing time would be
required.. I guess I need a better description of the voxel tree structure..
Thanks,         _Dan
...........................................................................

Fm: Dan Corritore/MOTM 70243,1110
To: Mark Betz/Ass't SysOp 76605,2346 (X)

Aaaaahhhhhh!!! Are we going around in circles, or what?!?<g> You said that
the tree would be divided into sections, each with either a null pointer, or
a linked list coming off of it, yes? That's exactly what the array would
be... an array of linked lists.. if Null, there's no list, so go to your next
location.. same with the tree, except it's more complicated, and takes more
time..  From what I've heard from you, it sounds to me that you are wasting
space both ways..   Thanks,
        _Dam
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Bob Provencher/GD SL 71621,2632 (X)

I think I'm beginning to see, Bob, but you lost me on:

>> So compute the octant of an rgb value, you simply decide whether it is the
>> second half of the line which describes the componant you're looking for.

>> So, for example, assuming a cube 63 on a side, the first octant for the
rgb >> value 32,32,32 is 1,1,1 or 7.  However, 31, 31, 31 is in octant 0,0,0.

and also I'm having trouble with the part about "rotating the bitfield that
represents the RGB value". It appears that you're letting each set bit
represent either 0, 2, or 4, and then adding them vertically. I don't get the
part about rotation. Must be missing something basic.

This is exciting. I definitely think you might be on to something. Is there a
possibility of a "collision" in this method? In other words, can two
different triplets produce the same octcode?
                                                        --Mark
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632
To: Mark Betz/Ass't SysOp 76605,2346 (X)

Hi Mark -

>> So compute the octant of an rgb value, you simply decide whether it is the
>> second half of the line which describes the componant you're looking for

For R,G and B lines of length 64 (0 through 63) if the value is 31, or less
that bit gets a zero, otherwise it gets a one.  Your just figuring out which
half of the line the value lies in.

>> So, for example, assuming a cube 63 on a side, the first octant for the
rgb >> value 32,32,32 is 1,1,1 or 7.  However, 31, 31, 31 is in octant 0,0,0.

If the total cube is the cube of sides with length 64, then a
"first-octant" is a subcube of the total cube.  32,32,32 lies in octant 7,
or binary 111 while 31,31,31 lies in octant 0, or binary 000.

>> I'm having trouble with the part about "rotating the bitfield that
>> represents the RGB valueif the RGB value is 64,64,64

R = 111111 = 64
G = 111111 = 64
B = 111111 = 64

Then to get the oct-code you just rotate the bitmap 90 degrees to the right

BGR
111 = 7
111 = 7
111 = 7
111 = 7
111 = 7
111 = 7

to get your oct-code.

I've been thinking about it further.  All we're really doing here is
allowing you to do a comparison on the R, G and B values, and give
them equal weight.  By rotating, we're saying that we want to find values in
the closest cube, not the closest color.  You can define exactly how large
your "closest cube" is by how many low oct-codes you ignore in an octcode.

I still think there is a problem with boundary values, but I have another
idea I'll tell you about tomorrow after I work it out.  The problem is
basically that if you're looking for the closest match to 32,32,32, and 31,
31, 31 exists in the pallette, this method wouldn't necesarily _ever_ find it
as the closest, because it's sort of an equal to or greater than comparison.

What we can do is also find the oct-codes for the seven combinations of RGB
values that are one less the the RGB values we're looking for, this will
give us those cubes that are to the left of the one we want.

For example for 32, 32, 32 we should really compute a quad code for

(32,32,32) - (0, 0, 0) = ( itself   ) = quadcode 700000
(32,32,32) - (0, 0, 1) = (32, 32, 31) = quadcode 344444
           -  0  1  0  =  32, 31, 32  =          522222
           -  0  1  1  =  32, 31, 31  =          166666
           -  1  0  0  =  31, 32, 32  =          611111
           -  1  0  1  =  31, 32, 31  =          255555
           -  1  1  0  =  31, 31, 32  =          433333
           -  1  1  1  =  31, 31, 31  =          077777

The problem is, even when you drop out the last octit(?) none of the ranges
fallout (become the same), but I think this is worst case.  If you take a
regular number at random you might find that some of the resulting codes are
the same after dropping the last octal digit.

This still adds up to the worst case 64 compares since now we're only
ignoring the last digit, not the last two, and comparing cubes to the left
as well as right.

I also see a problem with this if the closest match was greater than 2
away, then you'd have to ignore the last two octal digits and search for
matches.  No, maybe that would still be ok?

I'll play with it some more.

Bob
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346
To: Bob Provencher/GD SL 71621,2632 (X)

Oh, I see! That bit about the rotation was just too simple a concept for me
to grasp immediately <g>.

So producing the octcode is very straightforward, but I still don't
understand exactly what you're doing to the extent I'd need to to appreciate
the comments on boundary values. I need to look at it some more, but right
now I'm busy writing a set of small programs for the article. Tell you what,
if you can make it work for a palette lookup, I'll work it into the article
as an alternative technique, for which you will get full credit. Speaking of
which, I have to send you the tree code. Basically the test programs have to
be able to call two functions:

 void rgb_sort( char* dactable );
 int rgb_match( char r, char g, char b, int t );

The first simply does any initialization work. In my case it builds the tree,
and in yours it would calculate the octcodes and build the array. The second
finds and returns the palette index containing the closest match to the
passed color triplet. The 't' parameter is a threshold value that is specific
to my type of search algorithm. It's basically the vector range on each axis
that we spoke of the other night. You can ignore it.

I'l send the tree package along now, so that you have the latest copy of the
source code. It's very small, and hopefully very clear.

                                                        --Mark
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 284350
To: Hans Peter Rushworth 100031,473 (X)        Date: 23-Jan-93  17:16:43

Hi Peter -

I've just finished reading OCT.DOC.  I think there is some promise to the
method, based on the fact that the 64^3 grid is so sparsely populated, that
I wouldn't need to build the index match down to the sixth level in all
cases.

I can check for an entire cube having an exact index match by computing the
eight corners first, then if they are not equal, computing all the values.

I can readily adapt the idea of octcodes to your method, which means I won't
necessarily have the overhead of a tree, or I can implement it as a tree.

As you point out it may take quite a bit of memory, and I'm also wondering
if building the index values for the 64^3 space (given that we won't have to
compute all of these) will still take too long.

It does sound promising, though, I'm going to try it out, thanks!

One thing though, isn't the formula for computing the distance between to
three dimensional co-ordinates the square-root of the some of the squares of
the x, y and z differences, or sqr( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )?
...........................................................................

Fm: Hans Peter Rushworth 100031,473            # 284412
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 23-Jan-93  19:27:22

>> [distance =] sqr( (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 )?

That is right, my brain must have flipped.

>> I can check for an entire cube having an exact index match by computing
the eight corners first, then if they are not equal, computing all the values.

No Bob, If they are not equal, you have to bisect the cube into 8 more cubes
and repeat the test for each new cube recursively. You stop doing this when
all the corners are equal. The only time you actualy check all the points is
when the cube you have is 2x2x2, (obviously because in that case the 8 points
are all the points). Otherwise checking all the points would take a very long
time.

>> based on the fact that the 64^3 grid is so sparsely populated.

Well, it is fully populated (every colour has an index), the storage method
just identifies where the value changes from one to another, it is
effectively storing the boundaries of each clump of the same index in a way
that is easy to search.

>> I can readily adapt the idea of octcodes to your method, which means I
won't necessarily have the overhead of a tree, or I can implement it as a
tree.

I would do it as a tree first, just to make sure the scheme is correct.
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 284511
To: Hans Peter Rushworth 100031,473 (X)        Date: 23-Jan-93  22:22:08

>> No Bob, If they are not equal, you have to bisect the cube into 8 more
>> cubes and repeat the test for each new cube recursively. You stop doing
>> this when all

Right, I understood this but sort of typed something completely different
<g>.

>> Well, it is fully populated (every colour has an index), the storage
>> method just identifies where the value changes from one to another, it is
>> effectively storing the boundaries of each clump of the same index in a
>> way that is easy to search.

Right, but there will only be 256 different indexes in the tree.  In some
cases we may only have to search the tree to three levels (or match the
octcodes by the left three).  Worst case would of course be 6 levels, but
that shouldn't happen unless we have some adjacant or very close colors,
right?

>> I would do it as a tree first, just to make sure the scheme is correct.

You're right, it's easier to do it recursively first and worry about
implementation details later.
...........................................................................

Fm: Hans Peter Rushworth 100031,473            # 284548
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 23-Jan-93  23:46:33

>> Right, but there will only be 256 different indexes in the tree.  In some
cases we may only have to search the tree to three levels (or match the
octcodes by the left three).  Worst case would of course be 6 levels, but
that shouldn't happen unless we have some adjacant or very close colors,
right?

Right. It all depends on where the edges happen to be, you can get lucky.

BTW I have no justification for the "corner" algorithm. I thought of that
while I was writing that file. I've a Gut feeling it is correct, I suppose it
is rather like the 4-colour (or was it 3-colour) map problem. If it fails
then there is probably a faster way of searching for the nearest index. The
way this would work is that you only search indexes that are

(1) inside the cube being tested

(2) already lying along the edges of the cube (IOW test all points along each
of the edges of the cube).

Initially the search set is the entire 256 colour index set. At each level of
recursion, you reduce this by eliminating the cases that don't suceed the two
above tests. Typically this might reduce your colour index set from 256 to
256/8, which is a substantial saving. In fact it might be a good idea to use
this method in place of the 8-point test.

To expand on these tests, consider the following (contrived) quadtree
sub-node case:

   1 1 1 1 2 2 2 2
   1 * * * * * * 2
   1 * *(5)* * * 2
   1 * * * * * * 2
   4 * * *(6)* * 3
   4 * * * * * * 3
   4 * * * * * * 3
   4 4 4 3 3 3 3 3

You would search all the edge points finding the nearest index. In this case
you find indices 1-4. The indices 5 & 6 lie inside the quad. You can now
eliminate all the other indexes for subsequent recursive tests for the
points marked * and this will be much quicker than checking all 256 of the
indices. You should also be able to eliminate all internal indices (5 & 6)
that don't ALSO appear on an edge from ALL other tests.

This should speed the initial setup (tree)mendously.

Peter.
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 284803
To: Hans Peter Rushworth 100031,473 (X)        Date: 24-Jan-93  12:12:33

>> BTW I have no justification for the "corner" algorithm.

Yeah, it seems like it has to be right.  I couldn't prove it formally, but I
think it must ok.

>> (1) inside the cube being tested
>> (2) already lying along the edges of the cube (IOW test all points along
>> each of the edges of the cube).
>> Initially the search set is the entire 256 colour index set. A each
>> level of...

I think this sort of what I was trying to do before.  It failed whenever the
actual closest index fell just outside the cube.  It might have to be
extended to one-half the width of the cube.
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 285922
To: Hans Peter Rushworth 100031,473 (X)        Date: 26-Jan-93  00:07:09

I did send it to Bob. I think it was the source of his misery and lack of
time spent with his fiance <g>.

My implementation uses a binary space partitioning tree to partition the RGB
cube at each node. The compare key rotates with each level in the tree, such
that red is compared at level 0, green at level 1, blue at level 2, and so
on. The tree requires 2304 bytes for a 256-color palette, and another 1500
bytes or so for the code to build and search the tree. On my 486 it will
produce an accurate match in about .9 ms, depending on the depth of the
search path. I'm sure it could be made faster, since the nature of palette
data produces a pretty terrible looking binary tree. I'm using a staggered
insertion order when building the tree to avoid hitting any gradient ranges,
but I still get a very deep tree for some palettes. I'd like to know if
there's a way to balance a BSP tree. I suspect there isn't, since the
relative position of nodes in the tree is part of the information contained.
Have any ideas on this?

Btw, what's your schedule this weekend? I'd like to give you a call, and need
a good time. Could you PRI your number to me in case I can't find it?

                                                        --Mark
...........................................................................

Fm: Hans Peter Rushworth 100031,473            # 286098
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 26-Jan-93  11:20:56

>> I'd like to know if there's a way to balance a BSP tree.

I don't know if this helps in thinking about it, but three levels of BSP tree
can be equivalent to a single octree node.

In that case I would imagine the max depth of your tree is 18 (6x3), and that
sounds reasonable to me. I'm quite amazed that your tree uses only 2304
bytes, which is much less than I would have guessed, but I suppose that can
change depending on the colours that are actually in the palette.

>> the relative position of nodes in the tree is part of the information
contained.

One way to find out is to alter the ordering scheme (instead of R, G then B)
try B, G then R. To balance the tree try to pick the partition (R G or B)
that splits the tree with even "weight" on either side at any given level.
This heuristic won't always give the optimum balance, but is perhaps a good
place to start. Usually you will want to ensure that for three levels of the
tree you have selected an R G & B transition at least once. But Imagine also
a palette that has only Red and Green and no blue colours.
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 286162
To: Hans Peter Rushworth 100031,473            Date: 26-Jan-93  13:59:07

Hi, Peter. Interesting. Btw, the size of the tree doesn't change depending on
the colors in the palette. I don't look for duplicates: each triplet gets a
node. Each node consists of a triplet, two child pointers, and the index of
the original palette entry on which the node is based. Since the tree is
actually built in an array, the child pointers are 2-byte indices, and not 4
byte pointers, saving 2 words per node.

I think your estimate of the max depth is pretty close. Part of the
constraint of searching this kind of tree, is that you have to search both
subtrees anytime the current node falls within a "window" on either side of
the compare key. So for certain colors I end up searching 30-40 nodes. A lot
better than searching the whole palette, but there must be room for
improvement.
                                                        --Mark

________________________ Subj: VGA Transparency code ________________________

Fm: VOR Technologies Inc 71333,134             # 312076
To: ALL                                        Date: 11-Mar-93  10:23:25

All,

Does anyone know of some existing code or have a good algorthym for doing
blends/mixes/transparencies etc with the VGA Palette. There are a couple of
things though, given that i am using a static 256 color palette (256 colors
were chosen and cant be changed for this program). Does anyone know of an
algorythm for selecting a value for a color that shows through another color
(i.E. i have a red rectanlg

i place a blue one on top that i deem to be 50% trasnparent i should then be
able to choose something in the purple area). I know various graphics program
do it, but am not sure of an algorythm or existing code that might be
available.

Thanks,

Chris Eisnaugle Vor Technologies Inc.
...........................................................................

Fm: Jaimi McEntire 71700,1202                  # 312143
To: VOR Technologies Inc 71333,134 (X)         Date: 11-Mar-93  12:49:40

Chris,

   You could do it the "Cheesy" way... ie:    Multiply the transparent color
register (R,G,and B seperately) byt the transparency amount, multiply the
color which you're plotting on by the remainder, add the R from source and
dest, G from source and dst, and B from source and dest. then divide the
results by 100, and that should give you the optimum RGB. Then just search
through your palette to find the closest match.

    pixel = GetPixel(x,y)
    pixel.red *= transparency_perc;
    pixel.green *= transparency_perc;
    pixel.blue  *= transparency_perc;
    destpixel = GetPixel(destx,desty);
    destpixel.red *= (100-transparency_perc);
    destpixel.green *= (100-transparency_perc);
    destpixel.blue  *= (100-transparency_perc);
    optimum.red = (pixel.red + destpixel.red)/100;
    optimum.green = (pixel.green + destpixel.green)/100;
    optimum.blue  = (pixel.blue + destpixel.blue)/100;
    // now find optimum color in palette.
    // and set dest pixel to closest to optimum

Good luck!

P.S. this wont compile obviously. It's just an algorithm and a slow one.
     you could get much better performance if you used shifts, instead of
     divides, but then you would need to limit the transparency levels.

Jaimi McEntire
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 312351
To: VOR Technologies Inc 71333,134 (X)         Date: 11-Mar-93  20:36:07

Hi, Chris. If you want to put Jaimi's method to work, I have some code which
will select the best match for a given RGB from a palette. It builds a binary
search tree of color values, and takes about .10 ms to do a lookup on my
486-33. The code and data is about 5K.
                                                        --Mark
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 312780
To: VOR Technologies Inc 71333,134 (X)         Date: 12-Mar-93  21:26:44

I'll send it along tonight, Chris. The code is public domain, but I'd
appreciate it if you didn't distribute it until after July, since it is part
of an article that I have submitted to a magazine.


                                                        --Mark

___________________________ Subj: Mark's article ___________________________

Fm: Patrick Reilly 71333,2764                  # 376998
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 15-Jun-93  19:49:12

Mark,
  Thanks - I look forward to reading it (haven't gotten the last DDJ yet)...
  I was thinking about bitmap transforms; do you know if its possible,
probable, desirable, or already done <g> to take a square bitmap whose
elements are made up of a RGB triple and have a transform matrix that, if you
multiply your bitmap times it, will shade it for distance and do a "nice"
rotation/translation of it? IOW if you start out with, say, a 4x4 matrix
that's a bitmap that represents a (tiny) wall in RGB triplets when viewed
head-on at a distance of 0 - can a single matrix of RGBs be created that will
translate, rotate, and shade for distance the bitmap (with a specific RGB
quantity - say, <0,0,0> set to be 'transparent') so that if you now displayed
the bitmap, it would look like a 3D rendered texture of a wall that's 3 units
away and rotated about the vertical axis 60 degrees (with depth shading)?
  I was going to start playing with the idea (this would allow having all the
bitmaps for the walls, floors and ceilings loaded into memory, a list of
about 40 or so of these transform matrices, and drawing a 'world' would only
require doing the matrix multiply for each panel with the appropriate
transform, do another transform for the new bitmap's starting <x,y> location
on the screen, and displaying) but if this is 'old hat' <g> or has been tried
and found lacking, or is plain impossible, then I won't waste my time.
  I read Abrash's articles for X-Sharp, but for something like a fixed view
of panels which, in real-world coords, form a lattice, it seems that's not a
very good approach...
     -Pat-
...........................................................................

Fm: Patrick Reilly 71333,2764                  # 377238
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 16-Jun-93  00:17:25

Mark,
  I figured to use a lookup table to map the RGB triplet to a palette entry;
this would eliminate the problem of having to have the palette laid out so
that, for example, dark colors are near 0, light colors near 255, etc, but
would still allow having a triplet so that the transform matrix would make
'sense'. Also, multiplying the bitmap by a scalar would make sense too: IE
using a scalar of <0.75,0.75,0.75> would darken the whole bitmap evenly to
3/4 intensity. With a lookup table, I would think the conversion (from 1-byte
element matrix to RGB element matrix) would be quick enough. Of course, each
conversion would require a filter to 'round' the RGB value to the 'nearest'
mapping element.
  So you haven't heard of anyone trying this? I'll have to play a bit <g>;
what I would like to end up with is: 1) convert the NxN bitmap to an NxN RGB
matrix; 2) multiply the matrix by the appropriate transform matrix (IE if
this panel is the 'floor' at cell <-3,+4> from current POV, use
transformMatrix[18]); 3) use a filter on the transformed matrix so that the
RGB elements can map to palette entries; 4) convert the matrix back into a
bitmap; 5) look up the <x,y> pair for a floor at <-3,+4> from the POV and
paint the bitmap at <x,y>. If it *can* be done (ie one matrix will do the
complete conversion), then a nice, slow, floating-point program can generate
all the transforms and lookup tables for the <x,y> coords. Once these are
calculated, they can just be hardcoded into the program.
  I'll let you know if I can come up with anything.
       -Pat-
...........................................................................

Fm: Patrick Reilly 71333,2764                  # 377289
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 16-Jun-93  04:27:26

Mark,
  Oh well... its a no-show on a simple transform. A simple example shows why:
consider having a 4x4 bitmap (elements A(ij)), and wanting it to be
transformed onto the 'floor' panel immediately in front of the view plane;
what I'd want when the transform is complete would be for A(41) to have the
colors 0.65*(0.5*A(41) + 0.5*A(31)). To get such a product, the bitmap would
have to multiply on the right the transform matrix; but A(32) wants to be
0.03*A(31) + 0.5*A(32) + ..., which means that the bitmap has to multiply on
the *left* the transform matrix...

  I'll play some more; maybe its possible to use 2 matrices; one that
multiplies on the left and transforms/alias' vertical pixels, and one that
multiplies on the right and transforms/alias' horizontal pixels, then sum the
two resultant RGB bitmaps... The bummer is that now I'd have to store *twice*
as many matrices...
...........................................................................